Vehicle routing problem

Questa voce o sezione sull'argomento matematica è ritenuta da controllare.

Motivo: "solita" traduzione semiautomatica in cui le fonti non sono state riportate correttamente dalla voce di origine

---

Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti del progetto di riferimento.

Il problema del Vehicle Routing (VRP) è un problema di ottimizzazione combinatoria e programmazione intera che chiede "Qual è l'insieme ottimale di percorsi che una flotta di veicoli deve attraversare per consegnare a un dato insieme di clienti?" Generalizza il problema del commesso viaggiatore (TSP). Apparve per la prima volta in un articolo di George Dantzig e John Ramser nel 1959,^[1] in cui fu scritto il primo approccio algoritmico applicato alle consegne di benzina. Spesso il contesto è quello della consegna di merci situate in un deposito centrale a clienti che hanno effettuato ordini per tali merci. L'obiettivo del VRP è ridurre al minimo il costo totale del percorso. Nel 1964 Clarke e Wright migliorarono l'approccio di Dantzig e Ramser utilizzando un efficace algoritmo greedy chiamato algoritmo di risparmio ("avido").

Determinare la soluzione ottimale per VRP è NP-hard,^[2] quindi la dimensione dei problemi che possono essere risolti in modo ottimale utilizzando la programmazione matematica o l'ottimizzazione combinatoria può essere limitata. Pertanto, i risolutori commerciali tendono a utilizzare le euristiche a causa delle dimensioni e della frequenza dei VRP del mondo reale che devono risolvere.

Il VRP ha molte applicazioni dirette nell'industria. I fornitori di strumenti di routing VRP spesso affermano di poter offrire risparmi sui costi dal 5% al 30%.^[3]